package leetcode_core.leetcode_4;

import org.junit.Test;

import java.util.*;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2022年11月10日 19:16
 */
public class ShortestPathAllKeys {
    public final static char EMPTY_ROOM = '.';//代表空房间可以通过
    public final static char BLOCK = '#';//代表墙
    public final static char BEGIN = '@';//代表起点
    private boolean[][][] vis;
    private int[][] steps = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
    public int shortestPathAllKeys(String[] grid) {
        int n = grid.length;int m = grid[0].length();
        int keyNum = 0;int beginX = 0;int beginY = 0;
        for(int i = 0;i<n;i++){
            for(int j = 0;j<n;j++){
                char c = grid[i].charAt(j);
                if(Character.isLowerCase(c)){
                    keyNum++;
                }
                if(c == '@'){
                    beginX = i; beginY = j;
                }
            }
        }
        vis = new boolean[n][m][1<<keyNum];
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{beginX,beginY,0});
        vis[beginX][beginY][0] = true;
        int ans = 0;
        while (!q.isEmpty()){
            int size = q.size();
            for(int i = 0;i<size;i++){
                int[] head = q.poll();
                int x = head[0];int y =head[1];int status = head[2];
                if(status == (1<<keyNum)-1){
                    return ans;
                }
                for(int k= 0;k<4;k++){
                    int tx = x + steps[k][0];
                    int ty = y + steps[k][1];
                    if(tx < 0 || tx >= n || ty <0 || ty >=m){
                        continue;
                    }
                    char next = grid[tx].charAt(ty);
                    if (next == '#' || ((Character.isUpperCase(next)) && ((status >> (next - 'A')) & 1) == 0)) {
                        continue;
                    }
                    int nextStatus = status;
                    if(Character.isLowerCase(next)){
                        nextStatus |= 1<< (next-'a');
                    }
                    if(!vis[tx][ty][nextStatus]){
                        vis[tx][ty][nextStatus] = true;
                        q.offer(new int[]{tx,ty,nextStatus});
                    }
                }
            }
            ans++;
        }
        return -1;
    }

    @Test
    public void test(){
        System.out.println(shortestPathAllKeys(new String[]{"@.a..","###.#","b.A.B"}));
    }
}



class Solution {
    private int[] dirs = {-1, 0, 1, 0, -1};

    public int shortestPathAllKeys(String[] grid) {
        int m = grid.length, n = grid[0].length();
        int k = 0;
        int si = 0, sj = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                char c = grid[i].charAt(j);
                if (Character.isLowerCase(c)) {
                    // 累加钥匙数量
                    ++k;
                } else if (c == '@') {
                    // 起点
                    si = i;
                    sj = j;
                }
            }
        }
        Deque<int[]> q = new ArrayDeque<>();
        q.offer(new int[] {si, sj, 0});
        boolean[][][] vis = new boolean[m][n][1 << k];
        vis[si][sj][0] = true;
        int ans = 0;
        while (!q.isEmpty()) {
            for (int t = q.size(); t > 0; --t) {
                int[] p = q.poll();
                int i = p[0], j = p[1], state = p[2];
                // 找到所有钥匙，返回当前步数
                if (state == (1 << k) - 1) {
                    return ans;
                }
                // 往四个方向搜索
                for (int h = 0; h < 4; ++h) {
                    int x = i + dirs[h], y = j + dirs[h + 1];
                    // 在边界范围内
                    if (x >= 0 && x < m && y >= 0 && y < n) {
                        char c = grid[x].charAt(y);
                        // 是墙，或者是锁，但此时没有对应的钥匙，无法通过
                        if (c == '#' || (Character.isUpperCase(c) && ((state >> (c - 'A')) & 1) == 0)) {
                            continue;
                        }
                        int nxt = state;
                        // 是钥匙
                        if (Character.isLowerCase(c)) {
                            // 更新状态
                            nxt |= 1 << (c - 'a');
                        }
                        // 此状态未访问过，入队
                        if (!vis[x][y][nxt]) {
                            vis[x][y][nxt] = true;
                            q.offer(new int[] {x, y, nxt});
                        }
                    }
                }
            }
            // 步数加一
            ++ans;
        }
        return -1;
    }
}
